{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Binary Tree from Preorder and Inorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #array #hash-table #divide-and-conquer #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #数组 #哈希表 #分治 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: buildTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从前序与中序遍历序列构造二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数数组&nbsp;<code>preorder</code> 和 <code>inorder</code>&nbsp;，其中&nbsp;<code>preorder</code> 是二叉树的<strong>先序遍历</strong>， <code>inorder</code>&nbsp;是同一棵树的<strong>中序遍历</strong>，请构造二叉树并返回其根节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/tree.jpg\" style=\"height: 302px; width: 277px;\" />\n",
    "<pre>\n",
    "<strong>输入</strong><strong>:</strong> preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]\n",
    "<strong>输出:</strong> [3,9,20,null,null,15,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> preorder = [-1], inorder = [-1]\n",
    "<strong>输出:</strong> [-1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= preorder.length &lt;= 3000</code></li>\n",
    "\t<li><code>inorder.length == preorder.length</code></li>\n",
    "\t<li><code>-3000 &lt;= preorder[i], inorder[i] &lt;= 3000</code></li>\n",
    "\t<li><code>preorder</code>&nbsp;和&nbsp;<code>inorder</code>&nbsp;均 <strong>无重复</strong> 元素</li>\n",
    "\t<li><code>inorder</code>&nbsp;均出现在&nbsp;<code>preorder</code></li>\n",
    "\t<li><code>preorder</code>&nbsp;<strong>保证</strong> 为二叉树的前序遍历序列</li>\n",
    "\t<li><code>inorder</code>&nbsp;<strong>保证</strong> 为二叉树的中序遍历序列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-binary-tree-from-preorder-and-inorder-traversal](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-binary-tree-from-preorder-and-inorder-traversal](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,15,7]\\n[9,3,15,20,7]', '[-1]\\n[-1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        inorder = sorted(preorder)\n",
    "        def buildTree(preorder, inorder):\n",
    "            if preorder:\n",
    "                root = TreeNode(preorder[0])\n",
    "                i = inorder.index(preorder[0])\n",
    "                root.left = buildTree(preorder[1:i+1], inorder[:i])\n",
    "                root.right = buildTree(preorder[i+1:], inorder[i+1:])\n",
    "                return root\n",
    "            return\n",
    "\n",
    "        return buildTree(preorder, inorder)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        def buildTree(preorder: List[int]) -> Optional[TreeNode]:\n",
    "            if not preorder: return\n",
    "            root = TreeNode(val = preorder[0])\n",
    "            preorderLeft = []\n",
    "            preorderRight = []\n",
    "            for oneNode in preorder[1:]:\n",
    "                if oneNode < preorder[0]:\n",
    "                    preorderLeft.append(oneNode)\n",
    "                else:\n",
    "                    preorderRight.append(oneNode)\n",
    "            root.left = buildTree(preorderLeft)\n",
    "            root.right = buildTree(preorderRight)\n",
    "            return root\n",
    "        return buildTree(preorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:\n",
    "        # # 1. 二叉搜索树的中序遍历是递增的\n",
    "        # inorder = sorted(preorder)\n",
    "        # def buildTree(preorder, inorder):\n",
    "        #     if preorder:\n",
    "        #         root = TreeNode(preorder[0])\n",
    "        #         i = inorder.index(preorder[0])\n",
    "        #         root.left = buildTree(preorder[1:i+1], inorder[:i])\n",
    "        #         root.right = buildTree(preorder[i+1:], inorder[i+1:])\n",
    "        #         return root\n",
    "        #     return\n",
    "        # return buildTree(preorder, inorder)\n",
    "        # 2.小于根节点的都是左子树\n",
    "        def buildTree(preorder, start, end):\n",
    "            if start==end:return None\n",
    "            root = TreeNode(preorder[start])\n",
    "            leftEnd = start+1\n",
    "            while leftEnd<end and preorder[leftEnd]<preorder[start]:\n",
    "                leftEnd+=1\n",
    "            root.left = buildTree(preorder, start+1, leftEnd)\n",
    "            root.right = buildTree(preorder, leftEnd, end)\n",
    "            return root\n",
    "        return buildTree(preorder, 0, len(preorder))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, postorder, inorder):\n",
    "        if len(inorder) == 0:\n",
    "            return None\n",
    "        root = TreeNode(postorder.pop())\n",
    "        rootInorderIndex = inorder.index(root.val)\n",
    "        \n",
    "        leftInorder = inorder[:rootInorderIndex]\n",
    "        rightInorder = inorder[rootInorderIndex + 1:]\n",
    "        \n",
    "        root.right = self.dfs(postorder, rightInorder)\n",
    "        root.left = self.dfs(postorder, leftInorder)\n",
    "        return root\n",
    "    \n",
    "        \n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.dfs(postorder, inorder)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: 'List[int]', postorder: 'List[int]') -> 'TreeNode':\n",
    "        dic = {}\n",
    "        for i,ele in enumerate(inorder):\n",
    "            dic[ele] = i\n",
    "        head = None\n",
    "        stack = []\n",
    "        for i in range(len(postorder)-1,-1,-1):\n",
    "            if not head:\n",
    "                head = TreeNode(postorder[i])\n",
    "                stack.append(head)\n",
    "            else:\n",
    "                num = postorder[i]\n",
    "                idx = dic[num]\n",
    "                node = TreeNode(num)\n",
    "                if idx > dic[stack[-1].val]:\n",
    "                    stack[-1].right = node\n",
    "                else:\n",
    "                    u = stack.pop()\n",
    "                    while stack and dic[stack[-1].val] > idx:\n",
    "                        u = stack.pop()\n",
    "                    u.left = node\n",
    "                stack.append(node)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.helper(0, len(inorder)-1, 0, len(postorder)-1, inorder, postorder)\n",
    "\n",
    "    def helper(self, in_start, in_end, post_start, post_end, in_order, post_order):\n",
    "        if in_start > in_end or post_start > post_end:\n",
    "            return None\n",
    "        root = TreeNode(post_order[post_end])\n",
    "        rootIndex = post_end\n",
    "        for i in range(in_start, in_end+1):\n",
    "            if in_order[i] == post_order[rootIndex]:\n",
    "                rootIndex = i\n",
    "                break\n",
    "\n",
    "        root.left = self.helper(in_start, rootIndex-1, post_start, post_start+rootIndex-in_start-1, in_order, post_order)\n",
    "        root.right = self.helper(rootIndex+1, in_end, post_start+rootIndex-in_start, post_end-1, in_order, post_order)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helper(inorder, a, b, postorder, c, d):\n",
    "            if a > b:\n",
    "                return None\n",
    "            v = postorder[d]\n",
    "            root = TreeNode(v)\n",
    "            idx = a\n",
    "            for i in range(a, b + 1):\n",
    "                if inorder[i] == v:\n",
    "                    idx = i\n",
    "                    break\n",
    "            root.left = helper(inorder, a, idx - 1, postorder, c, c + idx - 1 - a)\n",
    "            root.right = helper(inorder, idx + 1, b, postorder, c + idx - a, d - 1)\n",
    "            return root\n",
    "        return helper(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not postorder:\n",
    "            return None\n",
    "        post_id = len(postorder) - 2\n",
    "        in_id = len(inorder) - 1\n",
    "        root = TreeNode(postorder[-1])\n",
    "        cur = root\n",
    "        visit = []\n",
    "        visit.append(cur)\n",
    "        while post_id >= 0:\n",
    "            if (cur.val == inorder[in_id]) :\n",
    "                while visit and visit[-1].val == inorder[in_id] :\n",
    "                    cur = visit.pop()\n",
    "                    in_id = in_id - 1\n",
    "                cur.left = TreeNode(postorder[post_id])\n",
    "                cur = cur.left\n",
    "                visit.append(cur)\n",
    "                post_id = post_id - 1\n",
    "            else :\n",
    "                cur.right = TreeNode(postorder[post_id])\n",
    "                cur = cur.right\n",
    "                visit.append(cur)\n",
    "                post_id = post_id - 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not postorder:\n",
    "            return None\n",
    "        if len(postorder) == 1:\n",
    "            d = TreeNode(postorder[0])\n",
    "            return d\n",
    "        if postorder == inorder:\n",
    "            prev = None\n",
    "            head = None\n",
    "            for i in inorder[::-1]:\n",
    "                d = TreeNode(i)\n",
    "                if not head:\n",
    "                    head = d\n",
    "                if prev:\n",
    "                    prev.left = d\n",
    "                prev = d\n",
    "            return head\n",
    "        if inorder[::-1] == postorder:\n",
    "            prev = None\n",
    "            head = None\n",
    "            for i in inorder:\n",
    "                d = TreeNode(i)\n",
    "                if not head:\n",
    "                    head = d\n",
    "                if prev:\n",
    "                    prev.right = d\n",
    "                prev = d\n",
    "            return head\n",
    "        d = TreeNode(postorder[-1])\n",
    "        root = inorder.index(postorder[-1])\n",
    "        left_inorder = inorder[0:root]\n",
    "        left_postorder = []\n",
    "        for i in postorder:\n",
    "            if i in left_inorder:\n",
    "                left_postorder.append(i)\n",
    "        right_inorder = inorder[root+1:]\n",
    "        right_postorder = []\n",
    "        for i in postorder:\n",
    "            if i in right_inorder:\n",
    "                right_postorder.append(i)\n",
    "        d.left = self.buildTree(left_inorder, left_postorder)\n",
    "        d.right = self.buildTree(right_inorder, right_postorder)\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not postorder:\n",
    "            return None\n",
    "        n = len(postorder)\n",
    "        root = TreeNode(postorder[n-1])\n",
    "        stack = [root]\n",
    "        inorderIndex = n-1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            node = stack[-1]\n",
    "            posValue = postorder[i]\n",
    "            if node.val!=inorder[inorderIndex]:\n",
    "                node.right = TreeNode(posValue)\n",
    "                stack.append(node.right)\n",
    "            else:\n",
    "                while stack and stack[-1].val==inorder[inorderIndex]:\n",
    "                    inorderIndex-=1\n",
    "                    node = stack.pop()\n",
    "                node.left = TreeNode(posValue)\n",
    "                stack.append(node.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root=TreeNode(postorder[-1])\n",
    "        cur=len(inorder)-1\n",
    "        stack=[root]\n",
    "        for i in range(len(postorder)-2,-1,-1):\n",
    "            newnode=TreeNode(postorder[i])\n",
    "            if stack[-1].val!=inorder[cur]:\n",
    "                stack[-1].right=newnode\n",
    "                stack.append(newnode)\n",
    "            else:\n",
    "                while stack and stack[-1].val==inorder[cur]:\n",
    "                    node=stack.pop()\n",
    "                    cur-=1\n",
    "                node.left=newnode\n",
    "                stack.append(newnode)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not postorder:\n",
    "            return None\n",
    "        \n",
    "        n = len(postorder)\n",
    "        root = TreeNode(postorder[n - 1])\n",
    "        stack = [root]\n",
    "        inorder_idx = n - 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            postorder_val = postorder[i]\n",
    "            node = stack[-1]\n",
    "            if node.val != inorder[inorder_idx]:\n",
    "                node.right = TreeNode(postorder_val)\n",
    "                stack.append(node.right)\n",
    "            else:\n",
    "                while stack and stack[-1].val == inorder[inorder_idx]:\n",
    "                    node = stack.pop()\n",
    "                    inorder_idx -= 1\n",
    "                node.left = TreeNode(postorder_val)\n",
    "                stack.append(node.left)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        stack = collections.deque()\n",
    "        n = len(postorder)\n",
    "        stack.append([(0, n), (0, n), None, 'root'])\n",
    "        ans = None\n",
    "        while stack:\n",
    "            # print(stack)\n",
    "            # func body\n",
    "            # func input\n",
    "            postorder_section, inorder_section, parent, flag = stack.pop()\n",
    "            # recursion boundary\n",
    "            if postorder_section[1] - postorder_section[0] < 1:\n",
    "                continue\n",
    "\n",
    "            # create node\n",
    "            val = postorder[postorder_section[1]-1]\n",
    "            x = TreeNode(val)\n",
    "\n",
    "            # divide lc and rc subtree\n",
    "            idx = inorder.index(val, inorder_section[0], inorder_section[1])\n",
    "            lc_len = idx - inorder_section[0]\n",
    "\n",
    "            lc_postorder_section = (postorder_section[0], postorder_section[0] + lc_len)\n",
    "            rc_postorder_section = (postorder_section[0] + lc_len, postorder_section[1]-1)\n",
    "\n",
    "            lc_inorder_section = (inorder_section[0], idx)\n",
    "            rc_inorder_section = (idx+1, inorder_section[1])\n",
    "\n",
    "            # call func for lc and rc\n",
    "            stack.append([rc_postorder_section, rc_inorder_section, x, 'rc'])\n",
    "            stack.append([lc_postorder_section, lc_inorder_section, x, 'lc'])\n",
    "\n",
    "\n",
    "            # return node\n",
    "            if flag == 'lc':\n",
    "                parent.left = x\n",
    "            elif flag == 'rc':\n",
    "                parent.right = x\n",
    "            elif flag == 'root':\n",
    "                ans = x\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(l, r):\n",
    "            if l == r: return None\n",
    "            idx = max(indices[l:r])[1]\n",
    "            return TreeNode(inorder[idx], build(l, idx), build(idx+1, r))\n",
    "\n",
    "        indices = [(postorder.index(x), i) for i,x in enumerate(inorder)]\n",
    "        return build(0, len(inorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def helper(in_left, in_right):\n",
    "            # 如果这里没有节点构造二叉树了，就结束\n",
    "            if in_left > in_right:\n",
    "                return None\n",
    "            \n",
    "            # 选择 post_idx 位置的元素作为当前子树根节点\n",
    "            val = postorder.pop()\n",
    "            root = TreeNode(val)\n",
    "\n",
    "            # 根据 root 所在位置分成左右两棵子树\n",
    "            index = idx_map[val]\n",
    " \n",
    "            # 构造右子树\n",
    "            root.right = helper(index + 1, in_right)\n",
    "            # 构造左子树\n",
    "            root.left = helper(in_left, index - 1)\n",
    "            return root\n",
    "        \n",
    "        # 建立（元素，下标）键值对的哈希表\n",
    "        idx_map = {val:idx for idx, val in enumerate(inorder)} \n",
    "        return helper(0, len(inorder) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        ind=dict(zip(inorder,range(len(inorder))))\n",
    "        postd=dict(zip(postorder,range(len(postorder))))\n",
    "        def func(inos,inoe,pos,poe):\n",
    "            if pos>poe or inos>inoe:\n",
    "                return None\n",
    "            else:\n",
    "                res=TreeNode()\n",
    "                res.val=postorder[poe]\n",
    "                lins=inos\n",
    "                line=ind[postorder[poe]]-1\n",
    "                rins=ind[postorder[poe]]+1\n",
    "                rine=inoe\n",
    "\n",
    "                lpos=pos\n",
    "                lpoe=pos+ind[postorder[poe]]-inos-1\n",
    "                rpos=lpoe+1\n",
    "                rpoe=poe-1\n",
    "                res.left=func(lins,line,lpos,lpoe)\n",
    "                res.right=func(rins,rine,rpos,rpoe)\n",
    "                return res\n",
    "        return func(0,len(inorder)-1,0,len(postorder)-1)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "            #print(inorder,postorder)\n",
    "            lenth = len(inorder)\n",
    "            if lenth==1: return TreeNode(inorder[0])\n",
    "            value = postorder.pop()\n",
    "            root = TreeNode(value)\n",
    "            for i in range(lenth):\n",
    "                if inorder[i]==value:\n",
    "                    index = i\n",
    "            if index >0:\n",
    "                lefti = collections.deque()\n",
    "                leftp = collections.deque()\n",
    "                for _ in range(index):\n",
    "                    lefti.append(inorder.popleft())\n",
    "                    leftp.append(postorder.popleft())\n",
    "                root.left = build(lefti, leftp)\n",
    "            if index<lenth-1:\n",
    "                inorder.popleft()\n",
    "                righti = inorder\n",
    "                rightp = postorder\n",
    "                root.right = build(righti, rightp)\n",
    "            return root\n",
    "        ans = build(collections.deque(inorder),collections.deque(postorder))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        stack = []\n",
    "        n = len(inorder)\n",
    "        stack.append(TreeNode(postorder[-1]))\n",
    "        i = n - 2\n",
    "        inorderIndex = n-1\n",
    "        root = stack[0]\n",
    "        while i >= 0:\n",
    "            father = stack[-1]\n",
    "            if father.val ==  inorder[inorderIndex]:\n",
    "                while stack and stack[-1].val == inorder[inorderIndex]:\n",
    "                    father = stack.pop()\n",
    "                    inorderIndex -= 1\n",
    "                \n",
    "                node = TreeNode(postorder[i])\n",
    "                father.left = node\n",
    "                i -= 1\n",
    "                stack.append(node)\n",
    "            else:\n",
    "                node = TreeNode(postorder[i])\n",
    "                father.right = node\n",
    "                i -= 1\n",
    "                stack.append(node)\n",
    "        \n",
    "        print(root)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = {}\n",
    "        self.post = []\n",
    "\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        self.memo = {val:key for key,val in enumerate(inorder)}\n",
    "        self.post = postorder\n",
    "        \n",
    "        root = self.helper(0,len(inorder)-1,0,len(self.post)-1)\n",
    "        print(root)\n",
    "        return root\n",
    "        #root.val = slef.post\n",
    "\n",
    "    def helper(self,istart,iend,pstart,pend):\n",
    "        if istart > iend or pstart >pend :\n",
    "            return None       \n",
    "        root = self.post[pend] #根节点的值\n",
    "        root_inde = self.memo[root] #根节点的索引\n",
    "        node =TreeNode(root)\n",
    "        node.left = self.helper(istart,root_inde-1,pstart,pstart+root_inde-1-istart)\n",
    "        node.right = self.helper(root_inde+1,iend,pstart+root_inde-istart,pend-1)#不能单个引用i中的索引到p中，在p中可以用 P种的索引+在i中计算出的距离，即p，i中的索引并不是固定的是相对的，相互引用的时候只能引用距离，root_inde属于i中的索引可以在i中直接引用，在p中不可以\n",
    "        #pstart+root_inde-istart,pend-1)\n",
    "        return node \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        self.now = len(postorder) - 1\n",
    "        dict_inorder = {}\n",
    "        for i in range(len(inorder)):\n",
    "            dict_inorder[inorder[i]] = i\n",
    "        return self.f(0, len(postorder) - 1, inorder, postorder, dict_inorder)\n",
    "    def f(self, start, end, inorder, postorder, dict_inorder):\n",
    "        if start > end:\n",
    "            return None\n",
    "        node = TreeNode(postorder[self.now])\n",
    "        self.now -= 1\n",
    "        index = dict_inorder[node.val]\n",
    "        node.right = self.f(index + 1, end, inorder, postorder, dict_inorder)\n",
    "        node.left = self.f(start, index - 1, inorder, postorder, dict_inorder)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        import numpy\n",
    "        ins = numpy.array(inorder)\n",
    "        pos = numpy.array(postorder)\n",
    "        def helper(l1, r1, l2, r2):\n",
    "            if l1 >= r1 or l2 >= r2:\n",
    "                return None\n",
    "            \n",
    "            val = pos[r2 - 1]\n",
    "\n",
    "            root = TreeNode(int(val))\n",
    "            # print(root)\n",
    "            idx = l1    \n",
    "            while idx < r1 and ins[idx] != val:\n",
    "                idx += 1\n",
    "    \n",
    "            distance = idx - l1\n",
    "            root.left = helper(l1, idx, l2, l2 + distance)\n",
    "            root.right = helper( idx+1, r1, l2+distance, r2-1)\n",
    "            return root\n",
    "        \n",
    "        return helper(0, len(ins), 0, len(pos))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import numpy\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "\n",
    "        def build_a_tree(l,r):\n",
    "            if l>r:\n",
    "                return\n",
    "            node = postorder.pop()\n",
    "            root = TreeNode(node)\n",
    "            indx = inorder.index(node)\n",
    "            root.right = build_a_tree(indx+1,r)\n",
    "            root.left = build_a_tree(l,indx-1)\n",
    "            return root\n",
    "            \n",
    "        return build_a_tree(0,len(inorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if postorder==[] or inorder==[]:\n",
    "            return None\n",
    "        rootValue=postorder.pop()\n",
    "        root=TreeNode(rootValue)\n",
    "        index=inorder.index(rootValue)\n",
    "        root.right=self.buildTree(inorder[index+1:],postorder)\n",
    "        root.left=self.buildTree(inorder[:index],postorder)\n",
    "        return root\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helper(inorder, postorder):\n",
    "            if not inorder or not postorder:\n",
    "                return None\n",
    "\n",
    "            root_val = postorder.pop()\n",
    "            root = TreeNode(root_val)\n",
    "            idx = inorder.index(root_val)\n",
    "            \n",
    "            root.right = helper(inorder[idx+1:],postorder)\n",
    "            root.left = helper(inorder[:idx], postorder)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return helper(inorder,postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        root = None\n",
    "        if inorder:\n",
    "            ind = inorder.index(postorder.pop())\n",
    "            root = TreeNode(inorder[ind])\n",
    "            root.right = self.buildTree(inorder[ind+1:], postorder)\n",
    "            root.left = self.buildTree(inorder[:ind], postorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        self.postorder = postorder\n",
    "        self.len = len(postorder)\n",
    "        return self.recursion(inorder)\n",
    "\n",
    "    def recursion(self, inorder):\n",
    "        if not inorder:\n",
    "            return None\n",
    "        rootValue = 0\n",
    "        rootIndex = 0\n",
    "        for i in range(-1, -self.len-1, -1):\n",
    "            if self.postorder[i] in inorder:\n",
    "                rootIndex = i\n",
    "                rootValue = self.postorder[i]\n",
    "                break\n",
    "        else:\n",
    "            return None\n",
    "        self.postorder.pop(rootIndex)\n",
    "        self.len -= 1\n",
    "        rootIndex = inorder.index(rootValue)\n",
    "        leftInorder = inorder[:rootIndex]\n",
    "        rightInorder = inorder[rootIndex+1:]\n",
    "        root = TreeNode(rootValue)\n",
    "        root.left = self.recursion(leftInorder)\n",
    "        root.right = self.recursion(rightInorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if inorder:\n",
    "            ind = inorder.index(postorder.pop())\n",
    "            root = TreeNode(inorder[ind])\n",
    "            root.right = self.buildTree(inorder[ind+1:], postorder)\n",
    "            root.left = self.buildTree(inorder[:ind], postorder)\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode()\n",
    "        if inorder == [] or postorder == []:\n",
    "            return None\n",
    "        root.val=postorder.pop()\n",
    "        key = root.val\n",
    "        flag = 0\n",
    "        for i in range(len(inorder)):\n",
    "            if key == inorder[i]:\n",
    "                flag = i\n",
    "        root.right = self.buildTree(inorder[flag+1:],postorder)\n",
    "        root.left = self.buildTree(inorder[0:flag],postorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(inorder)==0:\n",
    "            return None\n",
    "        else:\n",
    "            value = postorder.pop()\n",
    "            index = inorder.index(value)\n",
    "            root = TreeNode(val = value)\n",
    "            root.right = self.buildTree(inorder[index+1:],postorder)\n",
    "            root.left = self.buildTree(inorder[:index],postorder)\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        mem = {val: i for i, val in enumerate(inorder)}\n",
    "\n",
    "        def traverse(post_list, in_begin, in_end):\n",
    "            if not post_list:\n",
    "                return None\n",
    "            root = post_list[-1]\n",
    "            in_idx = mem[root]\n",
    "            left_len = in_idx - in_begin\n",
    "            right_len = in_end - in_begin - left_len\n",
    "            node = TreeNode(root)\n",
    "            node.left = traverse(post_list[0:left_len], in_begin, in_idx-1)\n",
    "            node.right = traverse(post_list[left_len:-1], in_idx+1, in_end)\n",
    "            return node\n",
    "\n",
    "        return traverse(postorder, 0, len(inorder)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode(postorder[-1])\n",
    "        self.inorderDic ={}\n",
    "        n = len(inorder)\n",
    "        for i in range(n):\n",
    "            self.inorderDic[inorder[i]] = i\n",
    "        def createTree(curPostorder):\n",
    "            postorder1 = []\n",
    "            postorder2 = []\n",
    "            rootVal = curPostorder.pop()\n",
    "            rootNode = TreeNode(rootVal)\n",
    "            for val in curPostorder:\n",
    "                if self.inorderDic[val] < self.inorderDic[rootVal]:\n",
    "                    postorder1.append(val)\n",
    "                else:\n",
    "                    postorder2.append(val)\n",
    "            if postorder1:\n",
    "                rootNode.left = createTree(postorder1)\n",
    "            if postorder2:\n",
    "                rootNode.right = createTree(postorder2)\n",
    "            return rootNode\n",
    "        return createTree(postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def judgeNode(split_list, preorder):\n",
    "            if len(split_list) == 1:  # 叶子结点则构造节点\n",
    "                node = TreeNode(split_list[0])\n",
    "                # print(split_list[0])\n",
    "                preorder.remove(split_list[0])\n",
    "                return node\n",
    "            elif len(split_list)>1:  # 不是叶子结点，则找出当前根节点\n",
    "                return constructNode(preorder[-1], preorder, split_list)\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        def constructNode(num, preorder, inorder):\n",
    "            # print(num)\n",
    "            node = TreeNode(num)\n",
    "            preorder.remove(num)\n",
    "            index = inorder.index(num)\n",
    "\n",
    "            # 划分中序的左右两段\n",
    "            split_left = inorder[:index]\n",
    "            split_right = inorder[index + 1:]\n",
    "            node.right = judgeNode(split_right, preorder)\n",
    "            node.left = judgeNode(split_left, preorder)\n",
    "            \n",
    "            return node\n",
    "\n",
    "        # 前序确定根节点，中序确定左右节点\n",
    "        head = constructNode(postorder[-1], postorder, inorder)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        \n",
    "\n",
    "        def helper(inorder, postorder):\n",
    "            if not postorder or ( postorder[-1] not in inorder ):\n",
    "                return  \n",
    "            value= postorder.pop()\n",
    "            head = TreeNode(value)\n",
    "            \n",
    "            \n",
    "            chaifen = inorder.index(value) # 拆分的点\n",
    "\n",
    "            right = inorder[chaifen:]\n",
    "            left = inorder[:chaifen+1]\n",
    "\n",
    "            \n",
    "            head.right = self.buildTree(right, postorder)\n",
    "            head.left = self.buildTree(left, postorder)\n",
    "            return head\n",
    "        return helper(inorder, postorder)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def helper(in_left, in_right):\n",
    "        #     # 如果这里没有节点构造二叉树了，就结束\n",
    "        #     if in_left > in_right:\n",
    "        #         return None\n",
    "            \n",
    "        #     # 选择 post_idx 位置的元素作为当前子树根节点\n",
    "        #     val = postorder.pop()\n",
    "        #     root = TreeNode(val)\n",
    "\n",
    "        #     # 根据 root 所在位置分成左右两棵子树\n",
    "        #     index = idx_map[val]\n",
    " \n",
    "        #     # 构造右子树\n",
    "        #     root.right = helper(index + 1, in_right)\n",
    "        #     # 构造左子树\n",
    "        #     root.left = helper(in_left, index - 1)\n",
    "        #     return root\n",
    "        \n",
    "        # # 建立（元素，下标）键值对的哈希表\n",
    "        # idx_map = {val:idx for idx, val in enumerate(inorder)} \n",
    "        # return helper(0, len(inorder) - 1)\n",
    "\n",
    "\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\r\n",
    "        if inorder:\r\n",
    "            idx = inorder.index(postorder.pop())\r\n",
    "            root = TreeNode(inorder[idx])\r\n",
    "            root.right = self.buildTree(inorder[idx+1:], postorder)\r\n",
    "            root.left = self.buildTree(inorder[:idx], postorder)\r\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not postorder:\n",
    "            return None\n",
    "        i = inorder.index(postorder[-1])\n",
    "        root=TreeNode(postorder[-1])\n",
    "        root.left=self.buildTree(inorder[:i], postorder[:i])\n",
    "        root.right=self.buildTree(inorder[i+1:],postorder[i:-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        \"\"\"\n",
    "        :type inorder: List[int]\n",
    "        :type postorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not postorder:\n",
    "            return []\n",
    "        def digui(root, postorder, inorder):\n",
    "            root.val = postorder[-1]\n",
    "            node = postorder[-1]\n",
    "            index = inorder.index(node)\n",
    "            #如果有左子树:\n",
    "            if index>0:\n",
    "                root.left = TreeNode(0)\n",
    "                digui(root.left, postorder[:index], inorder[:index])\n",
    "            #如果有右子树:    \n",
    "            if index<len(inorder)-1:\n",
    "                root.right = TreeNode(0)\n",
    "                digui(root.right, postorder[index:len(postorder)-1], inorder[index+1:])\n",
    "                \n",
    "        root = TreeNode(0)        \n",
    "        digui(root, postorder, inorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not len(inorder) or not len(postorder):\n",
    "            return None\n",
    "        nodeVal = postorder[-1]\n",
    "        node = TreeNode(nodeVal)\n",
    "        for idx, num in enumerate(inorder):\n",
    "            if num == nodeVal:\n",
    "                break\n",
    "        leftLen = idx\n",
    "        if leftLen:\n",
    "            node.left = self.buildTree(inorder[:leftLen], postorder[:leftLen])\n",
    "        rightLen = len(inorder) - leftLen - 1\n",
    "        if rightLen:\n",
    "            node.right = self.buildTree(inorder[idx+1:], postorder[leftLen:leftLen+rightLen])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def buildTree(self, inorder, postorder):\n",
    "        if not inorder and not postorder:\n",
    "            return None\n",
    "        root = postorder[-1]\n",
    "        for i in range(len(inorder)):\n",
    "            if inorder[i] == root:\n",
    "                break\n",
    "        left = self.buildTree(inorder[0:i],postorder[:i])\n",
    "        right = self.buildTree(inorder[1+i:],postorder[i:-1])\n",
    "        t = TreeNode(root)\n",
    "        t.left = left\n",
    "        t.right = right\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        if not inorder:return\n",
    "        else:\n",
    "            root = TreeNode(postorder[-1])\n",
    "            i = inorder.index(root.val)\n",
    "\n",
    "            root.left = self.buildTree(inorder[:i],postorder[:i])\n",
    "            root.right = self.buildTree(inorder[i+1:],postorder[i:-1])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(inorder) == 0:\n",
    "            return\n",
    "        if len(inorder) == 1:\n",
    "            return TreeNode(inorder[0])\n",
    "        \n",
    "        root_val = postorder[-1]\n",
    "        index = inorder.index(root_val)\n",
    "        left = self.buildTree(inorder[:index], postorder[:index])\n",
    "        right = self.buildTree(inorder[index+1:], postorder[index:-1])\n",
    "        return TreeNode(root_val, left, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not inorder:\n",
    "            return None\n",
    "        root=postorder[-1]\n",
    "        sep=inorder.index(root)\n",
    "        return TreeNode(root,self.buildTree(inorder[:sep],postorder[:sep]),self.buildTree(inorder[sep+1:],postorder[sep:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not postorder:\n",
    "            return None\n",
    "\n",
    "        root_val = postorder[-1]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        separate_idx = inorder.index(root_val)\n",
    "        separate_left = inorder[:separate_idx]\n",
    "        separate_right = inorder[separate_idx+1:]\n",
    "\n",
    "        postorder_left = postorder[:len(separate_left)]\n",
    "        postorder_right = postorder[len(separate_left):-1]\n",
    "\n",
    "        root.left = self.buildTree(separate_left, postorder_left)       \n",
    "        root.right = self.buildTree(separate_right, postorder_right)       \n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, preorder, inorder):\n",
    "        if len(inorder) == 0:\n",
    "            return None\n",
    "        root = TreeNode(preorder.pop(0))\n",
    "        rootInorderIndex = inorder.index(root.val)\n",
    "        \n",
    "        leftInorder = inorder[:rootInorderIndex]\n",
    "        rightInorder = inorder[rootInorderIndex + 1:]\n",
    "        root.left = self.dfs(preorder, leftInorder)\n",
    "        root.right = self.dfs(preorder, rightInorder)\n",
    "        return root\n",
    "        \n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.dfs(preorder, inorder)\n",
    "    \n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :type inorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "\t# construct hashmap mapping a value to its inorder index\n",
    "        idx = {} \n",
    "        for i, val in enumerate(inorder):\n",
    "            idx[val] = i \n",
    "\t\t\t\n",
    "\t# Iterate over preorder and construct the tree \n",
    "        stack = []\n",
    "        head = None\n",
    "        for val in preorder:\n",
    "            if not head:\n",
    "                head = TreeNode(val)\n",
    "                stack.append(head)\n",
    "            else:\n",
    "                node = TreeNode(val)\n",
    "                if idx[val] < idx[stack[-1].val]:\n",
    "                    stack[-1].left = node\n",
    "                else:\n",
    "                    while stack and idx[stack[-1].val] < idx[val]:\n",
    "                        u = stack.pop()\n",
    "                    u.right = node\n",
    "                stack.append(node)\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTreeNode(self,preorder,prestart,preend,inorder,instart,inend):\n",
    "        if prestart>preend or instart>inend:\n",
    "            return None\n",
    "        treenode = TreeNode(preorder[prestart])\n",
    "        for i in range(instart,inend+1):\n",
    "            if inorder[i]==preorder[prestart]:\n",
    "                treenode.left = self.buildTreeNode(preorder,prestart+1,prestart+i-instart,inorder,instart,i-1)\n",
    "                treenode.right = self.buildTreeNode(preorder,prestart+i-instart+1,preend,inorder,i+1,inend)\n",
    "        return treenode\n",
    "        \n",
    "        \n",
    "        \n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :type inorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        root = self.buildTreeNode(preorder,0,len(preorder)-1,inorder,0,len(inorder)-1)\n",
    "        \n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :type inorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "#         if len(preorder) == 0:\n",
    "#             return None\n",
    "#         out = TreeNode(preorder[0])\n",
    "#         dic = {}\n",
    "#         for i,ele in enumerate(inorder):\n",
    "#             dic[ele] = i\n",
    "#         for i in range(1,len(preorder)):\n",
    "#             num = preorder[i]\n",
    "#             idx = dic[num]\n",
    "#             root = out\n",
    "#             while 1:\n",
    "#                 if dic[root.val] < idx:\n",
    "#                     if root.right is None:\n",
    "#                         root.right = TreeNode(num)\n",
    "#                         break\n",
    "#                     root = root.right\n",
    "#                 else:\n",
    "#                     if root.left is None:\n",
    "#                         root.left = TreeNode(num)\n",
    "#                         break\n",
    "#                     root = root.left\n",
    "#         return out\n",
    "        \n",
    "        dic = {}\n",
    "        for i,ele in enumerate(inorder):\n",
    "            dic[ele] = i\n",
    "    \n",
    "        def func(st_pre, ed_pre, st_in, ed_in):\n",
    "            if st_pre > ed_pre:\n",
    "                return None\n",
    "            if st_pre == ed_pre:\n",
    "                return TreeNode(preorder[st_pre])\n",
    "            root = TreeNode(preorder[st_pre])\n",
    "            i = dic[preorder[st_pre]]\n",
    "            j = st_pre+1+i-st_in\n",
    "            root.left = func(st_pre+1,j-1,st_in,i-1)\n",
    "            root.right = func(j, ed_pre,i+1,ed_in)\n",
    "            return root\n",
    "        return func(0,len(preorder)-1,0,len(inorder)-1)\n",
    "        \n",
    "        # if len(preorder) == 0:\n",
    "        #     return None\n",
    "        # root = TreeNode(preorder[0])\n",
    "        # for i,ele in enumerate(inorder):\n",
    "        #     if ele == preorder[0]:\n",
    "        #         break\n",
    "        # left = inorder[:i]\n",
    "        # right = inorder[i+1:]\n",
    "        # l = set(left)\n",
    "        # pre_left = []\n",
    "        # pre_right = []\n",
    "        # for i in range(1,len(preorder)):\n",
    "        #     if preorder[i] in l:\n",
    "        #         pre_left.append(preorder[i])\n",
    "        #     else:\n",
    "        #         pre_right.append(preorder[i])\n",
    "        # root.left = self.buildTree(pre_left, left)\n",
    "        # root.right = self.buildTree(pre_right, right)\n",
    "        # return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        a=len(preorder)\n",
    "        b=len(inorder)\n",
    "        if not (a==b and a!=0):\n",
    "            return None\n",
    "        queue=[[0,a-1]]\n",
    "        head=TreeNode(preorder[0])\n",
    "        queuepoint=[head]\n",
    "        while queuepoint and queue:\n",
    "            a,b=queue.pop()\n",
    "            p=queuepoint.pop()\n",
    "            if a==b:\n",
    "                continue\n",
    "            index=inorder.index(p.val)\n",
    "            indexgo=preorder.index(p.val)\n",
    "            temstack=[]\n",
    "            if index-a > 0:\n",
    "                new=TreeNode(preorder[indexgo+1])\n",
    "                p.left=new\n",
    "                temstack.append([new,[a,index-1]])\n",
    "            if b-index > 0:\n",
    "                new=TreeNode(preorder[indexgo+index-a+1])\n",
    "                p.right=new\n",
    "                temstack.append([new,[index+1,b]])\n",
    "            for iten,qujian in temstack[::-1]:\n",
    "                queuepoint.append(iten)\n",
    "                queue.append(qujian)\n",
    "        return head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        # if not (preorder and inorder):\n",
    "        #     return None\n",
    "        # root=TreeNode(preorder[0])\n",
    "        # index_root=inorder.index(root.val)\n",
    "        # root.left=self.buildTree(preorder[1:index_root+1],inorder[:index_root])\n",
    "        # root.right=self.buildTree(preorder[index_root+1:],inorder[index_root+1:])\n",
    "        # return root\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root=TreeNode(preorder[0])\n",
    "        res=[root]\n",
    "        index=0\n",
    "        for i in range(1,len(preorder)):\n",
    "            temp=preorder[i]\n",
    "            node=res[-1]\n",
    "            if node.val!=inorder[index]:\n",
    "                node.left=TreeNode(temp)\n",
    "                res.append(node.left)\n",
    "            else:\n",
    "                while res and res[-1].val==inorder[index]:\n",
    "                    node=res.pop()\n",
    "                    index+=1\n",
    "                node.right=TreeNode(temp)\n",
    "                res.append(node.right)\n",
    "                \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(preorder[0])\n",
    "        stack = [root]\n",
    "        inorderIndex = 0\n",
    "        for i in range(1, len(preorder)):\n",
    "            preorderVal = preorder[i]\n",
    "            node = stack[-1]\n",
    "            if node.val != inorder[inorderIndex]:\n",
    "                node.left = TreeNode(preorderVal)\n",
    "                stack.append(node.left)\n",
    "            else:\n",
    "                while stack and stack[-1].val == inorder[inorderIndex]:\n",
    "                    node = stack.pop()\n",
    "                    inorderIndex += 1\n",
    "                node.right = TreeNode(preorderVal)\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        stack = [root] # 当前节点的所有还没有考虑过右子树的祖先的节点？？？？\n",
    "\n",
    "        inorderIndex = 0\n",
    "        for i in range(1,len(preorder)):\n",
    "            preorderVal = preorder[i]\n",
    "            node = stack[-1]\n",
    "            if node.val != inorder[inorderIndex]:\n",
    "                node.left = TreeNode(preorderVal)\n",
    "                stack.append(node.left)\n",
    "            else:\n",
    "                while stack and stack[-1].val == inorder[inorderIndex]:\n",
    "                    node = stack.pop()\n",
    "                    inorderIndex += 1\n",
    "                node.right = TreeNode(preorderVal)\n",
    "                stack.append(node.right)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        # def myBuildTree(inorder_left: int, inorder_right: int):\n",
    "        #     if inorder_left > inorder_right:\n",
    "        #         return None\n",
    "        #     val = preorder.pop(0)\n",
    "        #     root = TreeNode(val)\n",
    "        #     idx = index[val]\n",
    "        #     root.left = myBuildTree(inorder_left, idx-1)\n",
    "        #     root.right = myBuildTree(idx+1, inorder_right)\n",
    "        #     return root\n",
    "        # n = len(preorder)\n",
    "        # # 构造哈希映射，帮助我们快速定位根节点\n",
    "        # index = {element: i for i, element in enumerate(inorder)}\n",
    "        # return myBuildTree(0, n - 1)\n",
    "        \n",
    "\n",
    "\n",
    "        if not preorder: return\n",
    "        root = TreeNode(preorder[0])\n",
    "        stack = [root]\n",
    "        inorderIndex = 0\n",
    "        n = len(preorder)\n",
    "        for i in range(1, n):\n",
    "            node = stack[-1]\n",
    "            if node.val != inorder[inorderIndex]:\n",
    "                node.left = TreeNode(preorder[i])\n",
    "                stack.append(node.left)\n",
    "            else:\n",
    "                while stack and inorderIndex < n and stack[-1].val == inorder[inorderIndex]:\n",
    "                    node = stack.pop()\n",
    "                    inorderIndex += 1\n",
    "                node.right = TreeNode(preorder[i])\n",
    "                stack.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        ### iteration edition\n",
    "        n = len(preorder)\n",
    "        stack = collections.deque()\n",
    "        stack.append([[0, n], [0, n], None, 'as_root'])\n",
    "        ans = None\n",
    "        while stack:\n",
    "            # print(stack)\n",
    "            # func input\n",
    "            (pre_l, pre_r), (in_l, in_r), parent, flag = stack.pop()\n",
    "            if pre_r - pre_l > 0:\n",
    "                # create Node\n",
    "                val = preorder[pre_l]\n",
    "                x = TreeNode(val)\n",
    "                \n",
    "                # return None\n",
    "                if flag == 'as_lc':\n",
    "                    parent.left = x\n",
    "                elif flag == 'as_rc':\n",
    "                    parent.right = x\n",
    "                elif flag == 'as_root':\n",
    "                    ans = x\n",
    "                \n",
    "                # divide lc and rc subtree\n",
    "                idx = inorder.index(val, in_l, in_r)\n",
    "                lc_len = idx - in_l\n",
    "                rc_len = in_r - (idx+1)\n",
    "                \n",
    "                lc_pre_l, lc_pre_r = pre_l + 1, pre_l + 1 + lc_len\n",
    "                lc_in_l, lc_in_r = in_l, idx\n",
    "\n",
    "                rc_pre_l, rc_pre_r = lc_pre_r, pre_r\n",
    "                rc_in_l, rc_in_r = idx+1, in_r           \n",
    "                \n",
    "                # call func for rc\n",
    "                stack.append([[rc_pre_l, rc_pre_r], [rc_in_l, rc_in_r], x, 'as_rc'])\n",
    "                # call func for lc\n",
    "                stack.append([[lc_pre_l, lc_pre_r], [lc_in_l, lc_in_r], x, 'as_lc'])\n",
    "            # else recur boundary return None\n",
    "        return ans\n",
    "                \n",
    "\n",
    "    '''\n",
    "        ### recursion edition\n",
    "        # recur boundary\n",
    "        if not preorder:\n",
    "            return None\n",
    "        val = preorder[0]\n",
    "        idx = inorder.index(val)\n",
    "        # divide lc and rc subtree\n",
    "        # call func for lc and rc\n",
    "        left = self.buildTree(preorder[1: idx+1], inorder[:idx])\n",
    "        right = self.buildTree(preorder[idx+1:], inorder[idx+1:])\n",
    "        # create node\n",
    "        x = TreeNode(val, left, right)\n",
    "        # return node\n",
    "        return x\n",
    "    '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        def helper(pre_start, pre_end, in_start, in_end):\n",
    "            if pre_start > pre_end:\n",
    "                return None\n",
    "            root_val = preorder[pre_start]\n",
    "            root_index = inorder.index(root_val)\n",
    "            left_size = root_index - in_start\n",
    "\n",
    "            left = helper(pre_start + 1, pre_start + left_size, in_start, root_index - 1)\n",
    "            right = helper(pre_start + left_size + 1, pre_end, root_index + 1, in_end)\n",
    "\n",
    "            return TreeNode(val=root_val, left=left, right=right)\n",
    "\n",
    "        return helper(0, len(preorder) - 1, 0, len(inorder) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        def myBuildTree(pre_left: int, pre_right: int, in_left: int, in_right: int):\n",
    "            if pre_left > pre_right:\n",
    "                return None\n",
    "            \n",
    "            # 前序遍历中的第一个节点就是根节点\n",
    "            pre_root = pre_left\n",
    "            # 在中序遍历中定位根节点\n",
    "            in_root = index[preorder[pre_root]]\n",
    "            \n",
    "            # 先把根节点建立出来\n",
    "            root = TreeNode(preorder[pre_root])\n",
    "            # 得到左子树中的节点数目\n",
    "            size_left_subtree = in_root - in_left\n",
    "            # 递归地构造左子树，并连接到根节点\n",
    "            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素\n",
    "            root.left = myBuildTree(pre_left + 1, pre_left + size_left_subtree, in_left, in_root - 1)\n",
    "            # 递归地构造右子树，并连接到根节点\n",
    "            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素\n",
    "            root.right = myBuildTree(pre_left + size_left_subtree + 1, pre_right, in_root + 1, in_right)\n",
    "            return root\n",
    "        \n",
    "        n = len(preorder)\n",
    "        # 构造哈希映射，帮助我们快速定位根节点\n",
    "        index = {element: i for i, element in enumerate(inorder)}\n",
    "        return myBuildTree(0, n - 1, 0, n - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        \n",
    "        def build_from_idx(pre_st, pre_end, mid_st, mid_end):\n",
    "            # check\n",
    "            if pre_st > pre_end or mid_st > mid_end:\n",
    "                return None\n",
    "\n",
    "            mid_val = preorder[pre_st]\n",
    "            mid_node = TreeNode(mid_val)\n",
    "\n",
    "            mid_idx_inorder = None\n",
    "            for i in range(mid_st, mid_end + 1):\n",
    "                if inorder[i] == mid_val:\n",
    "                    mid_idx_inorder = i\n",
    "                    break\n",
    "            \n",
    "            next_mid_pair_left = mid_st, mid_idx_inorder - 1\n",
    "            next_mid_pair_right = mid_idx_inorder + 1, mid_end\n",
    "\n",
    "            left_cnt = mid_idx_inorder - mid_st\n",
    "            right_cnt = mid_end - mid_idx_inorder\n",
    "\n",
    "            next_pre_pair_left = pre_st + 1, pre_st + left_cnt\n",
    "            next_pre_pair_right = pre_st + left_cnt + 1, pre_end\n",
    "\n",
    "            mid_node.left = build_from_idx(next_pre_pair_left[0], next_pre_pair_left[1], next_mid_pair_left[0], next_mid_pair_left[1])\n",
    "            mid_node.right = build_from_idx(next_pre_pair_right[0], next_pre_pair_right[1], next_mid_pair_right[0], next_mid_pair_right[1])\n",
    "            return mid_node\n",
    "        \n",
    "        lens_pre = len(preorder)\n",
    "        lens_in = len(inorder)\n",
    "        return build_from_idx(0, lens_pre - 1, 0, lens_in - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(inorder: List[int], preorder: List[int]) -> Optional[TreeNode]:\n",
    "            #print(inorder,postorder)\n",
    "            lenth = len(inorder)\n",
    "            if lenth==1: return TreeNode(inorder[0])\n",
    "            value = preorder.popleft()\n",
    "            root = TreeNode(value)\n",
    "            for i in range(lenth):\n",
    "                if inorder[i]==value:\n",
    "                    index = i\n",
    "            if index >0:\n",
    "                lefti = collections.deque()\n",
    "                leftp = collections.deque()\n",
    "                for _ in range(index):\n",
    "                    lefti.append(inorder.popleft())\n",
    "                    leftp.append(preorder.popleft())\n",
    "                root.left = build(lefti, leftp)\n",
    "            if index<lenth-1:\n",
    "                inorder.popleft()\n",
    "                righti = inorder\n",
    "                rightp = preorder\n",
    "                root.right = build(righti, rightp)\n",
    "            return root\n",
    "        ans = build(collections.deque(inorder),collections.deque(preorder))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        # 根据先序遍历找到根节点，在中序遍历中找到该根节点，该根节点左右两边分别是左子树和右子树的中序遍历，\n",
    "        # 将该左子树和右子树对应的先序遍历找出来，这样就有两对子树。分别重复以上过程，递归即可。\n",
    "        def createHashtable(lst):\n",
    "            ht = [0]*6001\n",
    "            for i, v in enumerate(lst):\n",
    "                ht[v + 3000] = i\n",
    "            return ht\n",
    "\n",
    "        inorder_ht = createHashtable(inorder)\n",
    "        def _buildTree(pre_start, in_start, treelen):\n",
    "            # print(preorder[pre_start:pre_start+treelen], inorder[in_start:in_start+treelen])\n",
    "            if treelen <= 0:\n",
    "                return None\n",
    "            root = TreeNode(val=preorder[pre_start])\n",
    "            i = inorder_ht[root.val+3000]\n",
    "            ltreelen = i - in_start\n",
    "            rtreelen = in_start + treelen - i - 1\n",
    "            # print(\"left tree\", preorder[pre_start+1:pre_start+1+ltreelen], inorder[in_start:in_start+ltreelen])\n",
    "            # print(\"right tree\", preorder[pre_start+ltreelen+1:pre_start+ltreelen+1+rtreelen], inorder[i+1:i+1+rtreelen], \"\\n\")\n",
    "            root.left = _buildTree(pre_start+1, in_start, ltreelen)\n",
    "            root.right = _buildTree(pre_start+ltreelen+1, i+1, rtreelen)\n",
    "            return root\n",
    "        return _buildTree(0, 0, len(inorder))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "\n",
    "        def dfs(root, preorder, inorder):\n",
    "            \n",
    "            leftInorder = deque()\n",
    "            while inorder:\n",
    "                cur = inorder.popleft()\n",
    "                if cur == root.val: break\n",
    "                leftInorder.append(cur)\n",
    "            rightInorder = deque(inorder)\n",
    "\n",
    "            leftPreorder = deque()\n",
    "            rightPreorder = deque()\n",
    "            for i in range(len(leftInorder)):\n",
    "                leftPreorder.append(preorder.popleft())\n",
    "            for i in range(len(rightInorder)):\n",
    "                rightPreorder.append(preorder.popleft())\n",
    "\n",
    "            # Construct the left subtree\n",
    "            if len(leftPreorder) > 0:\n",
    "                root.left = TreeNode(leftPreorder.popleft())\n",
    "                dfs(root.left, leftPreorder, leftInorder)\n",
    "\n",
    "            # Construct the right subtree\n",
    "            if len(rightPreorder) > 0:\n",
    "                root.right = TreeNode(rightPreorder.popleft())\n",
    "                dfs(root.right, rightPreorder, rightInorder)\n",
    "        \n",
    "        if len(preorder) == 0: return None\n",
    "        preorder = deque(preorder)\n",
    "        inorder = deque(inorder)\n",
    "        root = TreeNode(preorder.popleft())\n",
    "        dfs(root, preorder, inorder)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def f(self, start, end, preorder, inorder, dict_inorder):\n",
    "        if start > end:\n",
    "            return None\n",
    "        node = TreeNode(preorder[self.now])\n",
    "        self.now += 1\n",
    "        index = dict_inorder[node.val]\n",
    "        node.left = self.f(start, index - 1, preorder, inorder, dict_inorder)\n",
    "        node.right = self.f(index + 1, end, preorder, inorder, dict_inorder)\n",
    "        return node\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        self.now = 0\n",
    "        dict_inorder = {}\n",
    "        for i in range(len(inorder)):\n",
    "            dict_inorder[inorder[i]] = i\n",
    "        return self.f(0, len(preorder) - 1, preorder, inorder, dict_inorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \n",
    "        def helper(inleft, inright):\n",
    "            nonlocal pre_idx\n",
    "            if inleft == inright:\n",
    "                return None\n",
    "            root = TreeNode(preorder[pre_idx])\n",
    "            in_idx = index_map[preorder[pre_idx]]\n",
    "\n",
    "            pre_idx += 1\n",
    "            root.left = helper(inleft,in_idx)\n",
    "            root.right = helper(in_idx+1, inright)\n",
    "            return root\n",
    "        \n",
    "\n",
    "        index_map = {val:idx for idx, val in enumerate(inorder)}\n",
    "        pre_idx = 0\n",
    "        return helper(0,len(inorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        def myTree(preorder_left,preorder_right,inorder_left,inorder_right):\n",
    "            if preorder_left>preorder_right:\n",
    "                return None\n",
    "            root_val=preorder[preorder_left]\n",
    "            inorder_root=index[root_val]\n",
    "            size=inorder_root-inorder_left\n",
    "            root=TreeNode(root_val)\n",
    "            root.left=myTree(preorder_left+1,preorder_left+size,inorder_left,inorder_left+size-1)\n",
    "            root.right=myTree(preorder_left+size+1,preorder_right,inorder_root+1,inorder_right)\n",
    "            return root\n",
    "        index={num:i for i,num in enumerate(inorder)}\n",
    "        n=len(preorder)\n",
    "        return myTree(0,n-1,0,n-1)\n",
    "\n",
    "        '''\n",
    "        def buildsub(A,B):\n",
    "            if len(A)==0:\n",
    "                return\n",
    "            root=TreeNode(A[0])\n",
    "            k=int(B.index(A[0]))\n",
    "            A1=A[1:1+k]\n",
    "            A2=A[1+k:]\n",
    "            B1=B[0:k]\n",
    "            B2=B[k+1:]\n",
    "            root.left=buildsub(A1,B1)\n",
    "            root.right=buildsub(A2,B2)\n",
    "            return root\n",
    "        r=buildsub(preorder,inorder)\n",
    "        return r\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :type inorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if inorder:\n",
    "            ind = inorder.index(preorder.pop(0))\n",
    "            root = TreeNode(inorder[ind])\n",
    "            root.left = self.buildTree(preorder, inorder[0:ind])\n",
    "            root.right = self.buildTree(preorder, inorder[ind+1:])\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :type inorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helper(preorder,inorder):\n",
    "            if not inorder:\n",
    "                return None\n",
    "\n",
    "            root_val = preorder.popleft()\n",
    "            root = TreeNode(root_val)\n",
    "\n",
    "            idx = inorder.index(root_val)\n",
    "\n",
    "            root.left  = helper(preorder,inorder[:idx])\n",
    "            root.right = helper(preorder,inorder[idx+1:])\n",
    "\n",
    "            return root\n",
    "        return helper(deque(preorder),inorder)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self,preorder,inorder):\n",
    "        if not preorder and not inorder:\n",
    "            return None\n",
    "        parentVal=preorder.pop(0)\n",
    "        node=TreeNode(parentVal)\n",
    "        resultLeft,leftLen,resultRight,rightLen,flag=[],0,[],0,0\n",
    "        for i in inorder:\n",
    "\n",
    "            if i==parentVal :\n",
    "                flag=1\n",
    "            elif flag==0:\n",
    "                resultLeft.append(i)\n",
    "                leftLen+=1\n",
    "            elif flag :\n",
    "                resultRight.append(i)\n",
    "                rightLen+=1\n",
    "        if leftLen==1:\n",
    "            node.left=TreeNode(resultLeft[0])\n",
    "            preorder.remove(resultLeft[0])\n",
    "        elif leftLen==0:\n",
    "            node.left=None\n",
    "        else:\n",
    "            node.left=self.buildTree(preorder,resultLeft)\n",
    "        if rightLen==1:\n",
    "            node.right=TreeNode(resultRight[0])\n",
    "            preorder.remove(resultRight[0])\n",
    "        elif rightLen==0:\n",
    "            node.right =None\n",
    "        else:\n",
    "            node.right=self.buildTree(preorder,resultRight)\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        1. 位于前序序列首部的元素必定是当前根节点，记为r\n",
    "        2. 在中序序列中，位于r左边的为r的左子树，位于r右边为右子树\n",
    "        3. 按上述规则递归\n",
    "    '''\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        if len(preorder) == 0: return\n",
    "        if preorder[0] not in inorder: return \n",
    "        root = TreeNode(preorder[0])\n",
    "        cur_root = preorder.pop(0)\n",
    "        root_index = inorder.index(cur_root)\n",
    "        root.left = self.buildTree(preorder, inorder[:root_index])\n",
    "        root.right = self.buildTree(preorder, inorder[root_index+1:])\n",
    "\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        if not preorder or not inorder:\n",
    "            return None\n",
    "        root_val = preorder.pop(0)\n",
    "        root = TreeNode(root_val)\n",
    "        idx = inorder.index(root_val)\n",
    "                \n",
    "        root.left = self.buildTree(preorder, inorder[:idx])\n",
    "        root.right = self.buildTree(preorder, inorder[(idx+1):])\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        if not inorder:\n",
    "            return None\n",
    "        mid = preorder.pop(0)\n",
    "        node = TreeNode(mid)\n",
    "        index = inorder.index(mid)\n",
    "        node.left = self.buildTree(preorder, inorder[:index])\n",
    "        node.right = self.buildTree(preorder, inorder[index+1:])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        def recur_func(inorder):\n",
    "            x = preorder.pop(0)  \n",
    "            node = TreeNode(x)  \n",
    "            idx = inorder.index(x)  \n",
    "            left_l = inorder[:idx] \n",
    "            right_l = inorder[idx+1:]\n",
    "            node.left = recur_func(left_l) if left_l else None  \n",
    "            node.right = recur_func(right_l) if right_l else None\n",
    "            return node\n",
    "\n",
    "        if not preorder or not inorder: return None\n",
    "        return recur_func(inorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(inorder) == 0:\n",
    "            return None\n",
    "        else:\n",
    "            num = preorder.pop(0)\n",
    "            index = inorder.index(num)\n",
    "            root = TreeNode(val = num)\n",
    "            root.left = self.buildTree(preorder,inorder[0:index])\n",
    "            root.right = self.buildTree(preorder,inorder[index+1:])\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        inorder_map = {val: i for i, val in enumerate(inorder)}\n",
    "\n",
    "        def traverse(prelist, in_begin, in_end):\n",
    "            if not prelist: return None\n",
    "            root = prelist[0]\n",
    "            root_in_idx = inorder_map[root]\n",
    "            left_len = root_in_idx - in_begin\n",
    "            right_len = in_end - in_begin - left_len\n",
    "            node = TreeNode(root)\n",
    "            node.left = traverse(prelist[1:left_len+1], in_begin, root_in_idx-1)\n",
    "            node.right = traverse(prelist[left_len+1:], root_in_idx+1, in_end)\n",
    "            return node\n",
    "\n",
    "        return traverse(preorder, 0, len(preorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def create_node(preorder: list, inorder: list):\n",
    "            if not inorder:\n",
    "                return None\n",
    "            cur_val = preorder.pop(0)\n",
    "            cur_val_ind = inorder.index(cur_val)\n",
    "            l_vals = [inorder[i] for i in range(len(inorder)) if i < cur_val_ind]\n",
    "            r_vals = [inorder[i] for i in range(len(inorder)) if i > cur_val_ind]\n",
    "            l_node = create_node(preorder, l_vals)\n",
    "            r_node = create_node(preorder, r_vals)\n",
    "            cur_node = TreeNode(cur_val, l_node, r_node)\n",
    "\n",
    "            return cur_node\n",
    "\n",
    "        root = create_node(preorder, inorder)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def judgeNode(split_list, preorder):\n",
    "            if len(split_list) == 1:  # 叶子结点则构造节点\n",
    "                node = TreeNode(split_list[0])\n",
    "                # print(split_list[0])\n",
    "                preorder.remove(split_list[0])\n",
    "                return node\n",
    "            elif len(split_list)>1:  # 不是叶子结点，则找出当前根节点\n",
    "                print(preorder[0])\n",
    "                return constructNode(preorder[0], preorder, split_list)\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        def constructNode(num, preorder, inorder):\n",
    "            # print(num)\n",
    "            node = TreeNode(num)\n",
    "            preorder.remove(num)\n",
    "            index = inorder.index(num)\n",
    "\n",
    "            # 划分中序的左右两段\n",
    "            split_left = inorder[:index]\n",
    "            split_right = inorder[index + 1:]\n",
    "            node.left = judgeNode(split_left, preorder)\n",
    "            node.right = judgeNode(split_right, preorder)\n",
    "            return node\n",
    "\n",
    "        # 前序确定根节点，中序确定左右节点\n",
    "        head = constructNode(preorder[0], preorder, inorder)\n",
    "        return head\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\r\n",
    "        if inorder:\r\n",
    "            idx = inorder.index(preorder.pop(0))\r\n",
    "            root = TreeNode(inorder[idx])\r\n",
    "            root.left = self.buildTree(preorder, inorder[0: idx])\r\n",
    "            root.right = self.buildTree(preorder, inorder[idx+1: ])\r\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        if len(inorder)==0:\n",
    "            return None\n",
    "        else:\n",
    "            \n",
    "            root = TreeNode(preorder.pop(0))\n",
    "            mid = inorder.index(root.val)\n",
    "            root.left = self.buildTree(preorder, inorder[:mid])\n",
    "            root.right = self.buildTree(preorder, inorder[mid+1:])\n",
    "        return root\n",
    "       \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :type inorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not preorder: return None\n",
    "        i = inorder.index(preorder[0])\n",
    "        root = TreeNode(preorder[0])\n",
    "        root.left = self.buildTree(preorder[1:1 + i], inorder[:i])\n",
    "        root.right = self.buildTree(preorder[1 + i:], inorder[i + 1:])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :type inorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        # print(preorder)\n",
    "        # print(inorder)\n",
    "        if len(preorder)==0:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        for i,num in enumerate(inorder):\n",
    "            if num==preorder[0]:\n",
    "                root.left = self.buildTree(preorder[1:i+1],inorder[:i])\n",
    "                root.right = self.buildTree(preorder[i+1:],inorder[i+1:])\n",
    "                break\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def create_node(preorder: List[int], inorder: List[int]):\n",
    "        if not preorder:\n",
    "            return None, list(), list()\n",
    "        node = TreeNode(preorder[0])\n",
    "        pos = inorder.index(node.val)\n",
    "        return (node, (preorder[1:pos + 1], inorder[0:pos]),\n",
    "                (preorder[pos + 1:], inorder[pos + 1:]))\n",
    "\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        stack = list()\n",
    "        root = self.create_node(preorder, inorder)\n",
    "        node = root\n",
    "        while node[0] or stack:\n",
    "            while node[0]:\n",
    "                stack.append(node)\n",
    "                left_node = self.create_node(*node[1])\n",
    "                node[0].left = left_node[0]\n",
    "                node = left_node\n",
    "            node = stack.pop()\n",
    "            right_node = self.create_node(*node[2])\n",
    "            node[0].right = right_node[0]\n",
    "            node = right_node\n",
    "        return root[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n",
    "        if(not preorder or len(preorder)==0):\n",
    "            return None\n",
    "        root_val=preorder[0]\n",
    "        root_index=inorder.index(root_val)\n",
    "        inorder_left=inorder[:root_index]\n",
    "        inorder_right=inorder[root_index+1:]\n",
    "        preorder_left=preorder[1:len(inorder_left)+1]\n",
    "        preorder_right=preorder[len(inorder_left)+1:]\n",
    "        root=TreeNode(root_val)\n",
    "        root.left=self.buildTree(preorder_left,inorder_left)\n",
    "        root.right=self.buildTree(preorder_right,inorder_right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        root=TreeNode(preorder[0])\n",
    "        seen={}\n",
    "        seen[root]=(preorder,inorder)\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            pnode=stack.pop(0)\n",
    "            preorder, inorder=seen[pnode]\n",
    "            i=0\n",
    "            while(inorder[i]!=preorder[0]):\n",
    "                i+=1\n",
    "            left=(preorder[1:1+i], inorder[0:i])\n",
    "            right=(preorder[1+i:], inorder[1+i:])\n",
    "            if len(left[0])==1:\n",
    "                pnode.left=TreeNode(left[0][0])\n",
    "            elif len(left[0])>1:\n",
    "                pnode.left=TreeNode(left[0][0])\n",
    "                seen[pnode.left]=left\n",
    "                stack.append(pnode.left)\n",
    "            if len(right[0])==1:\n",
    "                pnode.right=TreeNode(right[0][0])\n",
    "            elif len(right[0])>1:\n",
    "                pnode.right=TreeNode(right[0][0])\n",
    "                seen[pnode.right]=right\n",
    "                stack.append(pnode.right)\n",
    "            \n",
    "\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def helper(preorder, inorder):\n",
    "            if len(preorder) != len(inorder):\n",
    "                raise RuntimeError(f\"Preorder Inorder mismatched! {preorder} {inorder}\")\n",
    "            if len(preorder) < 1:\n",
    "                return None\n",
    "            if len(preorder) == 1:\n",
    "                return TreeNode(preorder[0])\n",
    "                \n",
    "            new_root = preorder[0]\n",
    "            left_child_len = inorder.index(new_root)\n",
    "\n",
    "            left_child = helper(preorder[1:left_child_len + 1], inorder[:left_child_len])\n",
    "            right_child = helper(preorder[left_child_len + 1:], inorder[left_child_len + 1:])\n",
    "\n",
    "            return TreeNode(preorder[0], left_child, right_child)\n",
    "        \n",
    "        return helper(preorder, inorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(preorder, inorder):\n",
    "            if len(preorder) == len(inorder) == 0:\n",
    "                return None\n",
    "\n",
    "            root_val = preorder[0]\n",
    "\n",
    "            idx = inorder.index(root_val)\n",
    "            \n",
    "            root = TreeNode(root_val)\n",
    "            root.left = dfs(preorder[1:1 + idx], inorder[:idx])\n",
    "            root.right = dfs(preorder[1+idx:], inorder[idx + 1:])\n",
    "            return root\n",
    "        \n",
    "        return dfs(preorder, inorder)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
